package main.java.indi.zyj.hot100;

import main.java.indi.zyj.hot100.base.ListNode;

public class _25_removeNthFromEnd {


    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode top = new ListNode(-1);
        top.next = head;
        ListNode pre = findEndK(top, n + 1);
        pre.next = pre.next.next;
        return top.next;
    }

    ListNode findEndK(ListNode head, int k) {

        ListNode p1 = head,  p2 = head;

        for (int i = 0; i < k; i++) {
            p1 = p1.next;
        }

        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }

        return p2;

    }

    ListNode findFromEnd(ListNode head, int k) {
        ListNode p1 = head;
        // p1 先走 k 步
        for (int i = 0; i < k; i++) {
            p1 = p1.next;
        }
        ListNode p2 = head;
        // p1 和 p2 同时走 n - k 步
        while (p1 != null) {
            p2 = p2.next;
            p1 = p1.next;
        }
        // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
        return p2;
    }
}
